class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    # def partition(self, head, x: int):
    #     list_smaller, list_bigger = [], []
    #     for nums in head:
    #         if nums < x:
    #             list_smaller.append(nums)
    #         else:
    #             list_bigger.append(nums)
    #     list_smaller.extend(list_bigger)
    #     return list_smaller

    def partition(self, head, x: int):
        if not head:
            return head
        p = head
        head = ListNode(0)
        link = None
        pre_g = None
        pre_l = head
        while p:
            if p.val < x:
                pre_l.next = p
                pre_l = pre_l.next
            else:
                if not link:
                    link = p
                    pre_g = p
                else:
                    pre_g.next = p
                    pre_g = pre_g.next

            p = p.next
        if pre_g:
            pre_g.next = None
        pre_l.next = link
        return head.next


a = Solution()
print(a.partition([1, 4, 3, 2, 5, 2], 3))